import random

power = random.randint(150, 200)
mod = random.getrandbits(32)

powers = [1]
for _ in range(10 ** 6 + 5):
    powers.append(powers[-1] * power % mod)

'''
t目标字符串,求s中出现t的次数
'''
s = "abc"
n = len(s)
hashing = [0] * (n + 1)

for i in range(n):
    hashing[i + 1] = (hashing[i] * power + ord(s[i])) % mod

def f(l, r):
    return (hashing[r + 1] - hashing[l] * powers[r + 1 - l]) % mod
